import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 082. 含有重复元素集合的组合
 * @author: WXY
 * @create: 2023-01-20 19:54
 * @Version 1.0
 **/
public class offer_twentyeight1_combinationSum2 {
    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        process(candidates, target, 0, 0,used);
        return ans;
    }

    private static void process(int[] candidates, int aim, int index, int sum, boolean[] used) {
        if (aim == sum) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < candidates.length && candidates[i] + sum <= aim; i++) {
            if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == false) {
                continue;
            }
            path.add(candidates[i]);
            used[i] = true;
            sum += candidates[i];
            process(candidates, aim, i + 1, sum, used);
            sum -= candidates[i];
            used[i] = false;
            path.remove(path.size() - 1);

        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 1, 2, 7, 6, 1, 5};
        int k = 8;
        List<List<Integer>> list = combinationSum2(arr, k);
        System.out.println(list);

    }
}
